import java.util.ArrayList;
import java.util.HashSet;
import java.util.TreeMap;
import java.util.TreeSet;

/** vstupni gramatika musi byt vlastni
 *
 * @author Zuzana Krejcova
 */
public abstract class ChomskehoNF
{
    public static Gramatika transformuj(Gramatika g)
    {
        TreeSet<String> netermy = new TreeSet(g.neterminaly);
        TreeMap<String, HashSet<ArrayList<String>>> novaPravidla = new TreeMap();
        for (String neterm : g.pravidla.keySet()) //pro vsechna pravidla
        {
            novaPravidla.put(neterm, new HashSet());
            for (ArrayList<String> pravidlo : g.pravidla.get(neterm))
            {                            //pokud je pravidlo tvaru..
                if (((pravidlo.size()==1) && g.terminaly.contains(pravidlo.get(0))) // neterm -> term
                   || ((pravidlo.size()==2) && (g.neterminaly.contains(pravidlo.get(0)) // neterm -> neterm neterm
                      && (g.neterminaly.contains(pravidlo.get(1)))))
                   || ((neterm.equals(g.koren)) && (pravidlo.get(0).equals("\u03B5")))) // koren -> eps
                {
                    novaPravidla.get(neterm).add(pravidlo); //pridej pravilo


                } else // netreba uvazovat neterm -> neterm, gram. je bez jednoduchych pravidel
                {      // neterm -> term neterm / neterm term / symbol........symbol
                    String novyNeterm;
                    ArrayList<String> pomPravidlo = new ArrayList();
                    HashSet<ArrayList<String>> pravaStrana = new HashSet();

                    if (pravidlo.size()==2) // neterm -> term neterm / neterm term
                    {
                        if (g.terminaly.contains(pravidlo.get(0)))
                        {
                            novyNeterm = "<"+pravidlo.get(0)+">";
                            pomPravidlo.add(novyNeterm);
                            if (!g.terminaly.contains(pravidlo.get(1)))
                            {
                                pomPravidlo.add(pravidlo.get(1));
                            } else
                            {
                                String novyNeterm2 = "<"+pravidlo.get(1)+">";
                                netermy.add(novyNeterm2);
                                pomPravidlo.add(novyNeterm2);
                            }
                        } else
                        {
                            novyNeterm = "<"+pravidlo.get(1)+">";
                            pomPravidlo.add(pravidlo.get(0));
                            pomPravidlo.add(novyNeterm);
                        }
                        novaPravidla.get(neterm).add(pomPravidlo); // pridat neterm -> neterm neterm
                        pomPravidlo = new ArrayList();

                        netermy.add(novyNeterm); // pridat <a> -> a
                        if (g.terminaly.contains(pravidlo.get(0)))
                        {
                            pomPravidlo.add(pravidlo.get(0));
                        } else
                        {
                            pomPravidlo.add(pravidlo.get(1));
                        }
                        pravaStrana.add(pomPravidlo);
                        novaPravidla.put(novyNeterm, pravaStrana);
                        pomPravidlo = new ArrayList();


                    } else // neterm -> symbol........symbol
                    {
                        pravaStrana = new HashSet(); // <x>->x zbytecna inicializace
                        pomPravidlo = new ArrayList();
                        if (!g.neterminaly.contains(pravidlo.get(0)))
                        {
                            novyNeterm = "<"+pravidlo.get(0)+">"; // <x>
                            netermy.add(novyNeterm);              // +<x>
                            pomPravidlo.add(pravidlo.get(0));     // [x]
                            pravaStrana.add(pomPravidlo);         // [[x]]
                            novaPravidla.put(novyNeterm, pravaStrana); // +<x>->x

                            pomPravidlo = new ArrayList();
                            pomPravidlo.add(novyNeterm); // [<x>]
                        } else
                        {
                            pomPravidlo.add(pravidlo.get(0));
                        }
                        novyNeterm = "<"; // <xxx>
                        for (String s : pravidlo.subList(1, pravidlo.size()))
                        {
                            novyNeterm += s;
                        }
                        novyNeterm += ">";
                        netermy.add(novyNeterm);
                        pomPravidlo.add(novyNeterm); // [<x><xxx>]
                        novaPravidla.get(neterm).add(pomPravidlo); // +n->[<x><xxx>]
                        for (int i=1;i<pravidlo.size()-1;i++)
                        {
                            //<xxxx>-><x><xxx> <x>->x
                            pravaStrana = new HashSet(); // <x>->x
                            pomPravidlo = new ArrayList();
                            if (!g.neterminaly.contains(pravidlo.get(i)))
                            {
                                novyNeterm = "<"+pravidlo.get(i)+">"; //<x>
                                netermy.add(novyNeterm);
                                pomPravidlo.add(pravidlo.get(i));
                                pravaStrana.add(pomPravidlo);
                                novaPravidla.put(novyNeterm, pravaStrana);

                                pravaStrana = new HashSet(); //<xxxx>-><x><xxx>
                                pomPravidlo = new ArrayList();
                                pomPravidlo.add(novyNeterm);
                            } else
                            {
                                pomPravidlo.add(pravidlo.get(i));
                            }
                            if ((pravidlo.subList(i+1, pravidlo.size()).size() > 1)
                                || g.terminaly.contains(pravidlo.get(i+1)))
                            {
                                novyNeterm = "<";          // <xxx>
                                for (String s : pravidlo.subList(i+1, pravidlo.size()))
                                {
                                    novyNeterm += s;
                                }
                                novyNeterm += ">";
                                netermy.add(novyNeterm);
                                pomPravidlo.add(novyNeterm);
                            } else
                            {
                                pomPravidlo.add(pravidlo.get(i+1));// [<x><xxx>]
                            }
                            pravaStrana.add(pomPravidlo); // [[<x><xxx>]]

                            novyNeterm = "<";          // <xxxx>
                            for (String s : pravidlo.subList(i, pravidlo.size()))
                            {
                                novyNeterm += s;
                            }
                            novyNeterm += ">";
                            novaPravidla.put(novyNeterm, pravaStrana); //+<xxxx>-><x><xxx>

                            if ((i+1)==(pravidlo.size()-1)) //posledni (<xx> -> <x><x>) pak =>
                            {
                                pravaStrana = new HashSet();
                                pomPravidlo = new ArrayList();
                                novyNeterm = "<"+pravidlo.get(i+1)+">";
                                netermy.add(novyNeterm);
                                pomPravidlo.add(pravidlo.get(i+1));
                                pravaStrana.add(pomPravidlo);
                                novaPravidla.put(novyNeterm, pravaStrana);
                            }
                        }
                    }
                }
            }
        }
        Gramatika ret = new Gramatika(netermy, new TreeSet(g.terminaly), g.koren, novaPravidla);
        return ret;
    }
}